package com.yitiao.data_algorithms.leetcode.editor.cn;

import com.yitiao.data_algorithms.leetcode.editor.cn.base.ListNode;

class SortList {
    // 2023-05-01 02:36:39
    public static void main(String[] args) {
        Solution solution = new SortList().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
    /**
     * <b>归并排序</b>
     * <p>快慢指针+合并有序链表</p>
     */
    class Solution {
        public ListNode sortList(ListNode head) {
            if (head == null || head.next == null)
                return head;
            // 对于偶数个节点，如果希望慢指针落在中心左边的节点，快指针要比慢指针的起点多一个
            // 如果希望落在中心右边，快慢指针同时开始
            ListNode fast = head.next;
            ListNode slow = head;
            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            }
            ListNode temp = slow.next;
            slow.next = null;
            ListNode left = sortList(head);
            ListNode right = sortList(temp);
            // 虚拟头节点
            ListNode h = new ListNode(0);
            ListNode res = h;

            while (left != null && right != null) {
                if (left.val < right.val) {
                    h.next = left;
                    left = left.next;
                } else {
                    h.next = right;
                    right = right.next;
                }
                h = h.next;
            }
            // 拼接剩余的多出的节点
            h.next = left != null ? left : right;
            return res.next;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}